#include <stdio.h>
#include <stdlib.h>

int* dp_value(int w[], int v[], int capacity, int number);

int main(int argc, char** args)
{
	int w[] = {2, 3, 4, 5};
	int v[] = {3, 4, 5, 6};
	int number = 4;
	int capacity = 8;
	int maxValue = 0;
	int* bestGoods = NULL;
	bestGoods = dp_value(w, v, capacity, number);

	fprintf(stdout, "Result: {");
	for (int i = 0; bestGoods[i] > 0; ++i)
	{
		maxValue += v[bestGoods[i] - 1];
		fprintf(stdout, " %d ", bestGoods[i]);
	}
	fprintf(stdout, "}\n");
	fprintf(stdout, "maxValue: %d\n", maxValue);
	return 0;
}

int* dp_value(int w[], int v[], int capacity, int number)
{
	int* bestGoods = (int*)calloc(number, sizeof(int));
	int index = 0;
	int row = number + 1;
	int column = capacity + 1;
	int maxValueTable[row][column];
	
	for (int i = 0; i < row; ++i)
	{
		maxValueTable[i][0] = 0;
	}
	
	for (int j = 0; j < column; ++j)
	{
		maxValueTable[0][j] = 0;
	}

	for (int i = 1; i < row; ++i)
	{
		for (int j = 1; j < column; ++j)
		{
			if (w[i] > j)  // 选不了
			{
				maxValueTable[i][j] = maxValueTable[i-1][j];
			}
			else
			{
				int v1 = maxValueTable[i-1][j];
				int v2 = maxValueTable[i-1][j-w[i+1]] + v[i+1];
				maxValueTable[i][j] = v1 >= v2 ? v1 : v2;
			}
		}
	}  // 填完，回溯

	for (int i = row - 1; i > 0; --i)
	{
		if (maxValueTable[i][column] == maxValueTable[i-1][column])
		{
			i -= 1;  // 没选
		}
		else
		{
			bestGoods[index++] = i;
			i -= 1;
			column -= w[i];
		}
	}

	return bestGoods;
}
